121. Best Time to Buy and Sell Stock

Description

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

info

You can read the full description here.

Solution 1

Approach

1. When the price of stock becomes more expensive than yesterday, maximum profit increases.
2. But if it becomes cheaper than yesterday, you need to consider 2 cases:
   1. Today's price is more expensive than minimum price.
   2. Today's price is cheaper than minimum price.
3. If it is Case 2, the basis of calculating maximum profit changes. So you need to update minimum price.

Implementation

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = 10001
        max_profit = 0

        for price in prices:
            if min_price > price:
                min_price = price

            if (price - min_price) > max_profit:
                max_profit = price - min_price

        return max_profit

Complexity Analysis

• $n$: length of prices
• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

---

Solutions from the Book

info

The original source of codes below is here.

Solution 2

Approach

1. Approach with Brute Force.

Implementation

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price = 0

        for i, price in enumerate(prices):
            for j in range(i, len(prices)):
                max_price = max(prices[j] - price, max_price)

        return max_price

Solution 3

Approach

1. Almost same with Solution 1
2. Initialize minimum value with sys.maximize.

Implementation

import sys
from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = sys.maxsize

        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)

        return profit